package dp.bag_problem;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-09-02 21:11
 */
public class is_0_1_bag {

    // dp定义：dp[i][j] 表示从 [0...i] 取任意个物品放入容量为j的背包中，可得到的最大的价值
    // 递推式：dp[i][j] = max(dp[i-1][j] , dp[i - 1][j - weight[i]] + value[i])  不选第i个物品 or 选第i个物品，取两者较大值
    // 初始化：dp[i][0] = 0、dp[0][j] = value[0]
    // 返回值: dp[len-1][bagSize]

    @Test
    public void test() {
        System.out.println(weightBag01bag(new int[]{15, 20, 30}, new int[]{1, 3, 4}, 4));
    }

    /**
     * 注意，传入的value和weight数组的元素都应该是升序的
     *
     * @param value   各背包的价值
     * @param weight  各背包的重量
     * @param bagSize 背包容量
     */
    public int weightBag01bag(int[] value, int[] weight, int bagSize) {
        int ge = weight.length;
        int[][] dp = new int[ge][bagSize + 1];

        // 初始化 dp[0][j]
        for (int j = weight[0]; j <= bagSize; j++) { // ***
            // 注意这里的j必须是从 weight[0] 开始而不是0开始
            // 因为如果从0开始，这时背包容量为0，所得到的最大价值也是0，而不是value[0]
            dp[0][j] = value[0];
        }
        // dp[i][0] 为0，不需要初始化

        // 填充dp数组（因为是求最大价值，所以先i后j还是先j后i都一样）
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) { // ***
                if (j < weight[i]) {
                    // 如果当前背包容量都没有物品i大，不能放入
                    dp[i][j] = dp[i - 1][j];
                }else{
                    // ***
                    // dp[i - 1][j - weight[i]] ，j - weight 是放入 第j个物品前对应容量下的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }

        for (int i = 0; i < ge; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }

        return dp[ge - 1][bagSize];
    }
}
